/* 
 * Convert Sorted Array to Binary Search Tree
 */

#include "../../func.h"

TreeNode *sortedArray(vector<int> &nums)
{
    return sortedArrayToBst(nums.begin(), nums.end());
}

template <typename RandomAccessIterator>
TreeNode *sortedArrayToBst(RandomAccessIterator first, RandomAccessIterator last)
{
    const auto length = distance(first, last);
    if (length <= 0)
        return nullptr;

    auto mid = first + length / 2;
    TreeNode *root = new TreeNode(*mid);
    root->left = sortedArrayToBst(first, mid);
    root->right = sortedArrayToBst(mid + 1, last);
    return root;
}